#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution 
{
    int recursion(TreeNode * cur, int depth)
    {
        if(cur == nullptr)
        {
            return depth - 1;
        }
        return max(recursion(cur->left, depth + 1), recursion(cur->right, depth + 1));
    }
public:
    int maxDepth(TreeNode* root) 
    {
        return recursion(root, 1);
    }
};

// 辅助函数：创建二叉树节点
TreeNode* createNode(int val) {
    return new TreeNode(val);
}

// 辅助函数：释放二叉树内存
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    Solution solution;
    
    // 测试案例1: LeetCode示例1 - [3,9,20,null,null,15,7]
    //       3
    //      / \
    //     9   20
    //        /  \
    //       15   7
    // 预期输出: 3
    cout << "测试案例1: [3,9,20,null,null,15,7]" << endl;
    TreeNode* root1 = createNode(3);
    root1->left = createNode(9);
    root1->right = createNode(20);
    root1->right->left = createNode(15);
    root1->right->right = createNode(7);
    
    int result1 = solution.maxDepth(root1);
    cout << "输出: " << result1 << endl;
    cout << "预期: 3" << endl << endl;
    
    // 测试案例2: LeetCode示例2 - [1,null,2]
    //   1
    //    \
    //     2
    // 预期输出: 2
    cout << "测试案例2: [1,null,2]" << endl;
    TreeNode* root2 = createNode(1);
    root2->right = createNode(2);
    
    int result2 = solution.maxDepth(root2);
    cout << "输出: " << result2 << endl;
    cout << "预期: 2" << endl << endl;
    
    // 测试案例3: 空树
    cout << "测试案例3: []" << endl;
    TreeNode* root3 = nullptr;
    
    int result3 = solution.maxDepth(root3);
    cout << "输出: " << result3 << endl;
    cout << "预期: 0" << endl << endl;
    
    // 测试案例4: 只有一个节点
    cout << "测试案例4: [1]" << endl;
    TreeNode* root4 = createNode(1);
    
    int result4 = solution.maxDepth(root4);
    cout << "输出: " << result4 << endl;
    cout << "预期: 1" << endl << endl;
    
    // 测试案例5: 完全二叉树
    //       1
    //      / \
    //     2   3
    //    / \ / \
    //   4  5 6  7
    // 预期输出: 3
    cout << "测试案例5: 完全二叉树 [1,2,3,4,5,6,7]" << endl;
    TreeNode* root5 = createNode(1);
    root5->left = createNode(2);
    root5->right = createNode(3);
    root5->left->left = createNode(4);
    root5->left->right = createNode(5);
    root5->right->left = createNode(6);
    root5->right->right = createNode(7);
    
    int result5 = solution.maxDepth(root5);
    cout << "输出: " << result5 << endl;
    cout << "预期: 3" << endl << endl;
    
    // 测试案例6: 左偏树
    //   1
    //  /
    // 2
    ///
    //3
    ///
    //4
    // 预期输出: 4
    cout << "测试案例6: 左偏树 [1,2,null,3,null,null,null,4]" << endl;
    TreeNode* root6 = createNode(1);
    root6->left = createNode(2);
    root6->left->left = createNode(3);
    root6->left->left->left = createNode(4);
    
    int result6 = solution.maxDepth(root6);
    cout << "输出: " << result6 << endl;
    cout << "预期: 4" << endl << endl;
    
    // 测试案例7: 右偏树
    // 1
    //  \
    //   2
    //    \
    //     3
    //      \
    //       4
    //        \
    //         5
    // 预期输出: 5
    cout << "测试案例7: 右偏树 [1,null,2,null,3,null,4,null,5]" << endl;
    TreeNode* root7 = createNode(1);
    root7->right = createNode(2);
    root7->right->right = createNode(3);
    root7->right->right->right = createNode(4);
    root7->right->right->right->right = createNode(5);
    
    int result7 = solution.maxDepth(root7);
    cout << "输出: " << result7 << endl;
    cout << "预期: 5" << endl << endl;
    
    // 测试案例8: 不平衡树
    //       1
    //      / \
    //     2   3
    //    /     \
    //   4       5
    //  /         \
    // 6           7
    //              \
    //               8
    // 预期输出: 5
    cout << "测试案例8: 不平衡树" << endl;
    TreeNode* root8 = createNode(1);
    root8->left = createNode(2);
    root8->right = createNode(3);
    root8->left->left = createNode(4);
    root8->right->right = createNode(5);
    root8->left->left->left = createNode(6);
    root8->right->right->right = createNode(7);
    root8->right->right->right->right = createNode(8);
    
    int result8 = solution.maxDepth(root8);
    cout << "输出: " << result8 << endl;
    cout << "预期: 5" << endl << endl;
    
    // 清理内存
    deleteTree(root1);
    deleteTree(root2);
    deleteTree(root4);
    deleteTree(root5);
    deleteTree(root6);
    deleteTree(root7);
    deleteTree(root8);
    // root3 是 nullptr，不需要删除
    
    return 0;
}